package org.liaohailong.victor;

import androidx.annotation.NonNull;
import androidx.annotation.Nullable;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * Author: liaohailong
 * Date: 2021/12/26
 * Time: 9:32
 * Description: Last Recent Used
 **/
public abstract class LruStudy<K, V> {
    private final long maxMemory;

    private long currentMemory = 0;
    private final LinkedList<K> queue = new LinkedList<>(); // 使用顺序
    private final HashMap<K, V> cache = new HashMap<>(); // 去重+存储

    public LruStudy(long maxMemory) {
        this.maxMemory = maxMemory;
    }

    abstract long sizeOf(V t);

    abstract void onTrim(V t);

    // 时间复杂度：O(1) ~ O(n)
    public void put(@NonNull K key, @NonNull V value) {
        if (cache.containsKey(key)) {
            // 换值，重新计算内存占用，不刷新使用率
            V old = cache.get(key);
            currentMemory += (sizeOf(value) - sizeOf(old));
        } else {
            // 增加一个新值
            queue.addLast(key);
            cache.put(key, value); // O(1) ~ O(n)/O(logN)
            currentMemory += sizeOf(value);
        }

        // do trim if necessary， O(n)
        trim();
    }

    public void trim() {
        while (currentMemory > maxMemory && !cache.isEmpty()) {
            K firstKey = queue.pollFirst();
            V firstValue = cache.remove(firstKey);
            long firstSize = sizeOf(firstValue);
            currentMemory -= firstSize;
            onTrim(firstValue);
        }
    }

    // 时间复杂度：On
    @Nullable
    public V get(@NonNull K key) {
        if (cache.containsKey(key)) { // O(1) ~ O(n)/O(logN)
            queue.remove(key); // O(n)
            queue.addLast(key); // O(1)
            return cache.get(key); // O(1) ~ O(n)/O(logN)
        }
        return null;
    }
}
